package 剑指II;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-25
 **/

public class Jz082含有重复元素集合的组合 {

    /**
     * 给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，
     * 找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。 
     * <p>
     * 示例 1:
     * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
     * 输出:
     * [
     * [1,1,6],
     * [1,2,5],
     * [1,7],
     * [2,6]
     * ]
     * 示例 2:
     * 输入: candidates = [2,5,2,1,2], target = 5,
     * 输出:
     * [
     * [1,2,2],
     * [5]
     * ]
     *  
     * 提示:
     * 1 <= candidates.length <= 100
     * 1 <= candidates[i] <= 50
     * 1 <= target <= 30
     */

    private List<List<Integer>> result = new ArrayList<>();
    private int target;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        this.target = target;
        Arrays.sort(candidates);
        this.dfs(candidates, 0, 0, new ArrayList<>());
        return this.result;
    }

    private void dfs(int[] arr, int index, int sum, List<Integer> path) {
        if (sum > this.target) {
            return;
        }
        if (sum == this.target) {
            this.result.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < arr.length; i++) {
            if (sum + arr[i] > this.target || (i > 0 && i > index && arr[i] == arr[i - 1])) {
                continue;
            }
            path.add(arr[i]);
            this.dfs(arr, i + 1, sum + arr[i], path);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Jz082含有重复元素集合的组合 n = new Jz082含有重复元素集合的组合();
        int[] arr = {10, 1, 2, 7, 6, 1, 5};
        List<List<Integer>> result = n.combinationSum2(arr, 8);
        System.out.println(JSON.toJSONString(result));
    }

}
